package 力扣_树算法.遍历.层序遍历扩展;

import java.util.*;

/**107. 二叉树的层序遍历 II
 * @author zx
 * @create 2022-04-12 21:31
 */
public class 二叉树的层序遍历II_107 {
    /**
     * void add(int index, E element)：
     * 将指定的元素插入到列表的指定位置(可选操作)。将当前位置的元素(如果有的话)和随后的元素向后移动(下标加 1)
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            //这个方法的作用介绍在上面
            res.add(0,level);
            //Collections.reverse(res);//自己觉得这个更好
        }
        return res;
    }


    public List<List<Integer>> levelOrderBottom2(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        helper1(root,0,res);
        return res;
    }

    private void helper1(TreeNode root, int level, List<List<Integer>> res){
        if(root == null){
            return;
        }
        //level：代表当前所在层
        if(res.size() == level){
            res.add(0,new ArrayList<Integer>());
        }
        //res.size()、level都是变化的,但(res.size()-level-1 == 0)
        //即每次都是将树的下一层元素头插到结果集
        res.get(res.size() - level - 1).add(root.val);
        helper(root.left,level + 1,res);
        helper(root.right,level + 1,res);
    }

    public List<List<Integer>> levelOrderBottom1(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        helper(root,0,res);
        //将102(层序遍历)结果集反转即可
        Collections.reverse(res);
        return res;
    }

    private void helper(TreeNode root, int level, List<List<Integer>> res){
        if(root == null){
            return;
        }
        //level：代表当前所在层
        if(res.size() == level){
            res.add(new ArrayList<Integer>());
        }
        res.get(level).add(root.val);
        helper(root.left,level + 1,res);
        helper(root.right,level + 1,res);
    }

}
